package Graph;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * @author yyq
 * @create 2022-01-17 12:26
 *
 *  图
 *  这里使用邻接表法
 */
public class Graph {
    // 节点
    HashMap<String,Integer> nodes;
    ArrayList<String> list;
    int[][] table;
    int edges;
    int nodeNum;

    int[] flag;

    public Graph(int n){
        nodes = new HashMap<String, Integer>(n);
        table = new int[n][n];
        flag = new int[n];
        list = new ArrayList<>(n);
        edges = 0;
        nodeNum  = 0;
    }

    // 深度优先遍历 需要辅助数组来确认节点是否被访问
    public void DFS(int a,int len){
        // 访问节点
        System.out.println(list.get(a));
        flag[a]=1;
        len--;
        // 结束条件 所有的节点都被访问了
        if(len==0){
            for (int i = 0; i < flag.length; i++) {
                flag[i]=0;
            }
            return;
        }
        // 查找该节点第一个相邻并且未访问的节点
        for (int i = 0; i < table[a].length; i++) {
            if(table[a][i]==1){
                if(flag[i]==0){
                    DFS(i,len);
                }
            }
        }
    }

    // BFS 广度优先遍历
    // 类似于层次遍历  需要辅助访问数组  和  队列
    public void BFS(int node){
        ArrayList<Integer>  queue= new ArrayList<>();
        queue.add(node);
        while(queue.size()!=0){
            int pos = queue.get(0);
            if(flag[pos]==0){
                System.out.println(list.get(pos));
                flag[pos]=1;
            }
            queue.remove(0);
            for (int i = 0; i < table[pos].length; i++) {
                if(table[pos][i]==1){
                    if(flag[i]==0){
                        queue.add(i);
                    }
                }
            }
        }
    }


    public void addNode(String s){
        nodes.put(s,nodeNum);
        list.add(s);
        nodeNum++;
    }

    public void addEdge(String a,String b){
        Integer pos1 = nodes.get(a);
        Integer pos2 = nodes.get(b);
        table[pos1][pos2]=1;
        table[pos2][pos1]=1;
        edges+=2;
    }

    public void showGraph(){
        for (int i = 0; i < table.length; i++) {
            for (int i1 = 0; i1 < table[0].length; i1++) {
                System.out.print(table[i][i1]+" ");
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        String[] s = {"A","B","C","D","E"};
        for (int i = 0; i < s.length; i++) {
            graph.addNode(s[i]);
        }
        graph.addEdge("A","B");
        graph.addEdge("A","C");
        graph.addEdge("B","C");
        graph.addEdge("B","D");
        graph.addEdge("B","E");

        graph.showGraph();

//        graph.DFS(4,5);
//        System.out.println("=====");
        graph.BFS(1);
    }



}
